808E - Selling Souvenirs - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=3e5+5;
struct node{
	int num,x,y;
}dis[M]; 
int a[3][N],num[3];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
bool cmp(int x,int y){
	return x>y; 
}
int ans[N];
signed main(){
	int n=read(),m=read();
	for(int i=1;i<=n;++i){
		int w=read()-1,c=read();
		a[w][++num[w]]=c;
	}
	for(int i=0;i<3;++i){
		sort(a[i]+1,a[i]+1+num[i],cmp);
	}
	for(int i=1;i<=m;++i){
		dis[i]=dis[i-1];
		if(i==1){
			if(a[0][dis[i-1].x+1]){
				dis[i].num=dis[i-1].num+a[0][dis[i-1].x+1];
				dis[i].x=dis[i-1].x+1;
				dis[i].y=dis[i-1].y;
			}
		} 
		else{
			 if(dis[i-1].num+a[0][dis[i-1].x+1]<dis[i-2].num+a[1][dis[i-2].y+1]&&a[1][dis[i-2].y+1]){
			 dis[i].num=dis[i-2].num+a[1][dis[i-2].y+1];
				dis[i].x=dis[i-2].x;
				dis[i].y=dis[i-2].y+1;
			 }
			 else if(a[0][dis[i-1].x+1]){
				dis[i].num=dis[i-1].num+a[0][dis[i-1].x+1];
				dis[i].x=dis[i-1].x+1;
				dis[i].y=dis[i-1].y;
			}
		}
	}
	for(int i=1;i<=num[2];++i){
		ans[i]=ans[i-1]+a[2][i];
	}
	for(int i=1;i<=min(m/3,num[2]);++i){
		dis[m].num=max(dis[m].num,dis[m-i*3].num+ans[i]);
	} 
	printf("%lld\n",dis[m].num);
	return 0;
}